package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/">
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [0,1,3]
 * 输出: 2
 * <p>
 * 示例 2:
 * <p>
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *  
 * <p>
 * 限制：
 * <p>
 * 1 <= 数组长度 <= 10000
 *
 * @author or2
 * @date 2021年09月22日 时间: 17:51
 */
public class Offer53$2 {
    public int missingNumber(int[] nums) {
        int length = nums.length;
        if (nums[length - 1] == length - 1) {
            return length;
        }
        int rightIndex = length;
        int leftIndex = 0;

        int midIndex;
        while (leftIndex < rightIndex) {
            midIndex = leftIndex + (rightIndex - leftIndex >> 1);
            if (nums[midIndex] == midIndex) {
                if (nums[midIndex + 1] != midIndex + 1) {
                    return nums[midIndex] + 1;
                }
                leftIndex = midIndex + 1;
            } else {
                rightIndex = midIndex;
            }
        }

        return 0;
    }

    public int ingenious(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        for (int i = 0; i <= nums.length; i++) {
            ans ^= i;
        }

        return ans;
    }
}
